package com.banding.sort;

import cn.hutool.core.util.StrUtil;

public class QuickSort {
    public static void sort(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }

    public static void sort(int[] nums, int start, int end) {
        // 若待排序区间长度为1，则直接返回
        if (start >= end) {
            return;
        }

        // 移动基准元素到正确位置，并返回该位置
        int pivotIndex = partition(nums, start, end);
        // System.out.println(StrUtil.format("partition({},{},{})", nums, start, end));
        sort(nums, start, pivotIndex - 1);
//        System.out.println(StrUtil.format("sort({},{},{})", nums, start, pivotIndex - 1));
        sort(nums, pivotIndex + 1, end);
//        System.out.println(StrUtil.format("sort({},{},{})", nums, pivotIndex + 1, end));
    }

    /**
     * 将待排序区间的第一个元素作为pivot，将其移动到正确位置，并返回该位置的索引
     *
     * @param nums  待排序数组
     * @param start 待排序区间起点
     * @param end   待排序区间终点
     * @return 基准元素最终位置
     */
    public static int partition(int[] nums, int start, int end) {
        // 选择待排序区间的第一个元素作为基准元素，将其值保存到临时变量
        int pivot = nums[start];

        // low 从左向右移动
        int low = start;

        // high 从右向左移动
        int high = end;

        while (low < high) {
            // high 从右向左移动，找到小于基准元素的元素
            while (low < high && nums[high] >= pivot) {
                high--;
            }
            // 找到后将值保存到low处
            nums[low] = nums[high];

            // low 从左向右移动，找到大于基准元素的元素
            while (low < high && nums[low] <= pivot) {
                low++;
            }

            // 找到后将值保存到high处
            nums[high] = nums[low];
        }
        // 直到low和high相遇，将基准值保存至该位置
        nums[low] = pivot;

        return low;
    }


}
